package dp;

import javafx.util.Pair;

import java.util.HashSet;
import java.util.Set;

/**
 * 97. 交错字符串
 */
public class P97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        Set<Pair<Integer, Integer>> stateSet = new HashSet<>();
        stateSet.add(new Pair<>(0, 0));
        for (int i = 0; i < s3.length(); i++) {
            char c = s3.charAt(i);
            Set<Pair<Integer, Integer>> newStateSet = new HashSet<>();
            for (Pair<Integer, Integer> state : stateSet) {
                int x1 = state.getKey();
                int x2 = state.getValue();
                if (x1 < s1.length() && s1.charAt(x1) == c) {
                    newStateSet.add(new Pair<>(x1 + 1, x2));
                }
                if (x2 < s2.length() && s2.charAt(x2) == c) {
                    newStateSet.add(new Pair<>(x1, x2 + 1));
                }
            }
            stateSet = newStateSet;
            if (stateSet.size() == 0 && i < s3.length()) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        boolean interleave = new P97().isInterleave("aabcc", "dbbca", "aadbbbaccc");
        System.out.println(interleave);
    }


}
